/**
 * Copyright (c) 2010 CCX(China) Co.,Ltd. All Rights Reserved.
 *
 * This software is the confidential and proprietary information of
 * CCX(China) Co.,Ltd. ("Confidential Information").
 * It may not be copied or reproduced in any manner without the express 
 * written permission of CCX(China) Co.,Ltd.
 *
 * Author				: Administrator
 * Date					: 2010-8-24 09:20:38
 * Version 				: 1.0
 */
package com.comment;

/**
 * 在序列中查找指定元素，比较多种方法的实现效率 实现方法：普通循环法和二分法
 * 
 * Project : TEST 
 * JDK version used : jdk1.6 
 * Author : Administrator
 * 
 * Modified By： 
 * Modified Date： 
 * Why & What is modified：
 */
public class DichotomyComment {

	// 在此数字序列中查找指定数字
	int[] iArray = { 1, 5, 9, 14, 27, 39, 41, 50, 62, 222, 345, 612, 981, 1207, 8721 };
	int iSeek = 345; // 待查找的数字
	int iCount = 0; // 查找的次数

	/**
	 * 使用普通的循环方法查找指定数字的位置
	 * 
	 * @param anIntVar
	 *            待查找的数字
	 * @return int 查找次数
	 */
	public int loop(int anIntVar) {
		for (int i = 0; i < iArray.length; i++) {
			iCount++;
			if (anIntVar == iArray[i])
				break;
		}

		return iCount;
	}

	/**
	 * 使用二分法查找指定数字的位置
	 * 
	 * @return
	 * @throws Exception
	 */
	public int dichotomy() throws Exception {
		int iIndex = 0; // 位置索引
		int iStart = 0; // 开始查找的位置
		int iEnd = iArray.length - 1; // 查找结束的位置

		// 定义区间，取区间的中点，
		// 直到满足精度要求为止
		while (true) {
			iCount++;
			iIndex = (iStart + iEnd) / 2;
			if (iArray[iIndex] < iSeek) {
				iStart = iIndex;
			} else if (iArray[iIndex] > iSeek) {
				iEnd = iIndex;
			} else {
				break;
			}
		}

		return iCount;
	}

	// 重要的公共类，每次修改须添加以下注释
	// Rewriter：<修改人>
	// Rewrite Date：<修改日期：格式YYYY-MM-DD>
	// Start1：
	/* 
	 * 注释原代码内容，
	 * 使用块注释方式 ,
	 * 也可使用行头注释方式
	 */
	// End1：

	// 将原代码内容注释掉，然后添加新代码使用以下注释：
	// Added by：<修改人>
	// Add date：<添加日期，格式：YYYY-MM-DD>
	// Start2：
	/* 在此添加新代码 */
	// End2：

	public static void main(String[] args) {

		DichotomyComment dc = new DichotomyComment();
		DichotomyComment dc1 = new DichotomyComment();
		
		try {
			System.out.println("普通的循环查找，需要比较的次数：\t" + dc.loop(345));
			System.out.println("二分法查找，需要比较的次数：\t" + dc1.dichotomy());
			
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

}
